package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 将有序数组转换为二叉搜索树
 * <p>
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 按 严格递增 顺序排列
 * @date 2025/2/28 10:31
 */
public class SortedArrayToBST_108 {

    public static void main(String[] args) {
    }

    /**
     * 个解：dfs-递归
     * <p>
     * 思路：
     * 1.BST的中序遍历结果是严格有序，而题目也告知nums是升序
     * 2.要转换成一棵平衡BST，考虑使用分割的方式构造二叉树：本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
     * 3.注意边界处理。
     */
    public TreeNode sortedArrayToBST2(int[] nums) {
        return dfs2(nums, 0, nums.length - 1);
    }

    // 左闭右闭
    public TreeNode dfs2(int[] nums, int startIndex, int endIndex) {
        if (endIndex < startIndex) return null;

        // 根
        int index = startIndex + (endIndex - startIndex) / 2;
        TreeNode node = new TreeNode(nums[index]);
        // 叶子
        if (startIndex == endIndex) return node;

        // 左；[startIndex, index - 1]
        int leftStart = startIndex;
        int leftEnd = index - 1;
        TreeNode left = dfs2(nums, leftStart, leftEnd);

        // 右；[index + 1, endIndex]
        int rightStart = index + 1;
        int rightEnd = endIndex;
        TreeNode right = dfs2(nums, rightStart, rightEnd);

        node.left = left;
        node.right = right;
        return node;
    }

    /**
     * 官解-递归
     *
     * 上述个解的简化版
     */
    public TreeNode buildTree(int[] nums, int left, int right) {
        if (left > right) return null;

        // 选择左边节点为根节点
        int mid = left + (right - left) / 2;
        TreeNode treeNode = new TreeNode(nums[mid]);
        treeNode.left = buildTree(nums, left, --mid);
        treeNode.right = buildTree(nums, ++mid, right);
        return treeNode;
    }

}
